'''
给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点
'''

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        global valueIndex
        valueIndex = {}
        for i in range(len(inorder)):
            valueIndex[inorder[i]] = i
        return self.bulid(preorder,0,len(preorder)-1,inorder,0,len(inorder)-1)



    def bulid(self,preorder,prestart,preend,inorder,instart,inend):
        global valueIndex
        if prestart > preend:
            return None
        
        rootVal = preorder[prestart]
        index = valueIndex[rootVal]
        # index = 0
        # for i in range(len(inorder)):
        #     if inorder[index] == rootVal:
        #         index = i
        #         break
        
        left = index - instart
        root = TreeNode(rootVal)
        
        root.left = self.bulid(preorder,prestart+1,prestart + left,inorder,instart,index - 1)
        root.right = self.bulid(preorder,prestart+left+1,preend,inorder,index+1,inend)

        return root

        
        